#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
//typedef struct btnode
//{
//	char btdata;
//	struct btnode* plch;
//	struct btnode* prch;
//}btn;
//struct node
//{
//	btn* data;
//	struct node* next;
//};
//typedef struct linkqueue
//{
//	struct node* f;
//	struct node* r;
//}lq;
//lq* queueinit()
//{
//	lq* pq = (lq*)malloc(sizeof(lq));
//	if (pq == NULL)
//	{
//		printf("malloc fail");
//		return NULL;
//	}
//	pq->f = (struct node*)malloc(sizeof(struct node));
//	if (pq->f == NULL)
//	{
//		free(pq);
//		return NULL;
//	}
//	pq->r = pq->f;
//	pq->f->next = NULL;
//	return pq;
//}
//bool is_empty(lq* pq)
//{
//	if (pq->f == pq->r)
//		return true;
//	else
//		return false;
//}
//bool enqueue(lq* pq, btn* d)
//{
//	struct node* newnode = (struct node*)malloc(sizeof(struct node));
//	if (newnode == NULL)
//	{
//		printf("malloc fail");
//		return false;
//	}
//	newnode->data = d;
//	newnode->next = NULL;
//	pq->r->next = newnode;
//	pq->r = newnode;
//	return true;
//}
//bool outqueue(lq* pq, btn** val)
//{
//	if (is_empty(pq))
//		return false;
//	*val = pq->f->next->data;
//	struct node* tmp = pq->f->next;
//	pq->f->next = tmp->next;
//	if (pq->f->next == NULL)
//		pq->r = pq->f;
//	tmp->next = NULL;
//	free(tmp);
//	return true;
//}
//btn* create_tree()
//{
//	btn* pa, * pb, * pc, * pd, * pe;
//	pa = (btn*)malloc(sizeof(btn));
//	pb = (btn*)malloc(sizeof(btn));
//	pc = (btn*)malloc(sizeof(btn));
//	pd = (btn*)malloc(sizeof(btn));
//	pe = (btn*)malloc(sizeof(btn));
//
//	pa->plch = pb;
//	pa->prch = pc;
//	
//	pb->plch = pd;
//	pb->prch = pe;
//	
//	pc->plch = NULL;
//	pc->prch = NULL;
//	
//	pd->plch = NULL;
//	pd->prch = NULL;
//	
//	pe->plch = NULL;
//	pe->prch = NULL;
//
//	pa->btdata = 'a';
//	pb->btdata = 'b';
//	pc->btdata = 'c';
//	pd->btdata = 'd';
//	pe->btdata = 'e';
//	return pa;
//}
//void level_show(btn* proot)
//{
//	lq* pq = queueinit();
//	btn* tmp = proot;
//	enqueue(pq, tmp);
//	while (!is_empty(pq))
//	{
//		outqueue(pq, &tmp);
//		if (tmp != NULL)
//		{
//			printf("%c", tmp->btdata);
//			if (tmp->plch != NULL)
//				enqueue(pq, tmp->plch);
//			if (tmp->prch != NULL)
//				enqueue(pq, tmp->prch);
//		}
//	}
//}
//void qian_show(btn* proot)
//{
//	if (proot != NULL)
//	{
//		printf("%c\t", proot->btdata);
//		if (proot->plch != NULL)
//			qian_show(proot->plch);
//		if (proot->prch != NULL)
//			qian_show(proot->prch);
//	}
//}
//int main()
//{
//	btn* proot = create_tree();
//	//level_show(proot);
//	qian_show(proot);
//	return 0;
//}
//struct student
//{
//	int order;
//	char name[30];
//};
//struct node
//{
//	struct student data;
//	struct node* next;
//};
//typedef struct linkqueue
//{
//	struct node* front;
//	struct node* rear;
//}lq;
//lq* queueinit()
//{
//	lq* pq = (lq*)malloc(sizeof(lq));
//	if (pq == NULL)
//	{
//		printf("malloc fail\n");
//		return NULL;
//	}
//	pq->front = pq->rear = NULL;
//	return pq;
//}
//bool is_empty(lq* pq)
//{
//	if (pq->front == NULL && pq->rear == NULL)
//		return true;
//	else
//		return false;
//}
//bool enqueue(lq* pq, int o, char* n)
//{
//	struct node* newnode = (struct node*)malloc(sizeof(struct node));
//	if (newnode == NULL)
//	{
//		printf("malloc fail\n");
//		return false;
//	}
//	newnode->data.order = o;
//	strcpy(newnode->data.name, n);
//	newnode->next = NULL;
//	if (is_empty(pq))
//	{
//		pq->front = pq->rear = newnode;
//	}
//	else
//	{
//		pq->rear->next = newnode;
//		pq->rear = newnode;
//	}
//	return true;
//}
//bool outqueue(lq* pq, struct student* val)
//{
//	if (is_empty(pq))
//		return false;
//	*val = pq->front->data;
//	struct node* tmp = pq->front->next;
//	pq->front->next = NULL;
//	free(pq->front);
//	pq->front = tmp;
//	if (pq->front == NULL)
//		pq->rear = pq->front;
//	return true;
//}
//void show(lq* pq)
//{
//	if (is_empty(pq))
//		return;
//	struct node* tmp = pq->front;
//	while (tmp != pq->rear)
//	{
//		printf("num:%d name:%s", tmp->data.order, tmp->data.name);
//		tmp = tmp->next;
//	}
//	printf("num:%d name:%s", pq->rear->data.order, pq->rear->data.name);
//}
//void destory(lq* pq)
//{
//	if (is_empty(pq))
//		return;
//	struct node* tmp = pq->front;
//	struct node* q = pq->front->next;
//	while (tmp != pq->rear)
//	{
//		free(tmp);
//		tmp = q;
//		q = q->next;
//	}
//	free(pq->rear);
//	pq->front = pq->rear = NULL;
//}
//int main()
//{
//	int order = 0;
//	struct student c;
//	char name[30] = { 0 };
//	int num = 0;
//	lq* pq = queueinit();
//	while (1)
//	{
//		printf("1 2 3 4");
//		scanf("%d", &num);
//		switch (num)
//		{
//		case 1:
//			printf("name");
//			scanf("%s", name);
//			enqueue(pq, ++order, name);
//			break;
//		case 2:
//			outqueue(pq, &c);
//			printf("num:%d name:%s", c.order, c.name);
//			break;
//		case 3:
//			show(pq);
//			break;
//		case 4:
//			destory(pq);
//			order = 0;
//			break;
//		default :
//			printf("num is invaild ");
//		}
//	}
//	return 0;
//}
//typedef struct dancer
//{
//	char sex;
//	char name[30];
//}dan;
//typedef struct loop_queue
//{
//	dan* d;
//	int f;
//	int r;
//}lq;
//#define SIZE 10
//lq* queueinit()
//{
//	lq* pq = (lq*)malloc(sizeof(lq));
//	if (pq == NULL)
//	{
//		printf("malloc fail");
//		return NULL;
//	}
//	pq->d = (dan*)malloc(sizeof(dan) * SIZE);
//	if (pq->d == NULL)
//	{
//		free(pq);
//		return NULL;
//	}
//	pq->f = pq->r = 0;
//	return pq;
//}
//bool is_empty(lq* pq)
//{
//	if (pq->f == pq->r)
//		return true;
//	else
//		return false;
//}
//bool is_full(lq* pq)
//{
//    if(pq->f == ((pq->r + 1)% SIZE))
//		return true;
//	else
//		return false;
//}
//bool enqueue(lq* pq, dan d)
//{
//	if (is_full(pq))
//		return false;
//	pq->d[pq->r] = d;
//	pq->r = (pq->r + 1) % SIZE;
//	return true;
//}
//bool outqueue(lq* pq, dan* d)
//{
//	if (is_empty(pq))
//		return false;
//	*d = pq->d[pq->f];
//	pq->f = (pq->f + 1) % SIZE;
//	return true;
//}
//bool get_head(lq* pq, dan* d)
//{
//	if (is_empty(pq))
//		return false;
//	*d = pq->d[pq->f];
//	return true;
//}
//void match(dan* dancer, int num)
//{
//	lq* fq = queueinit();
//	lq* mq = queueinit();
//	dan d;
//	int i = 0;
//	for (i = 0; i < num; i++)
//	{
//		d = dancer[i];
//		if (d.sex == 'f')
//			enqueue(fq, d);
//		else
//			enqueue(mq, d);
//	}
//	while(!is_empty(fq) && !is_empty(mq))
//	{
//		outqueue(fq, &d);
//		printf("%s ", d.name);
//		outqueue(mq, &d);
//		printf("%s \n", d.name);
//	}
//	if (!is_empty(fq))
//	{
//		get_head(fq, &d);
//		printf("%s\n", d.name);
//	}
//	if (!is_empty(mq))
//	{
//		get_head(mq, &d);
//		printf("%s\n", d.name);
//	}
//}
//int main()
//{
//	dan dancer[5];
//	int i = 0;
//	for (i = 0; i < 5; i++)
//	{
//		printf("di %d ge ren", i);
//		scanf("%s %c", &dancer[i].name, &(dancer[i].sex));
//		getchar();
//	}
//	match(dancer, 5);
//	return 0;
//}
typedef struct btnode
{
	char btdata;
	struct btnode* plch;
	struct btnode* prch;
}btn;
struct node
{
	btn* data;
	struct node* next;
};
typedef struct linkqueue
{
	struct node* f;
	struct node* r;
}lq;
lq* queueinit()
{
	lq* pq = (lq*)malloc(sizeof(lq));
	if (pq == NULL)
	{
		printf("malloc fail\n");
		return NULL;
	}
	pq->f = (struct node*)malloc(sizeof(struct node));
	if (pq->f == NULL)
	{
		free(pq);
		return NULL;
	}
	pq->r = pq->f;
	pq->f->next = NULL;
	return pq;
}
bool is_empty(lq* pq)
{
	if (pq->f == pq->r)
		return true;
	else
		return false;
}
bool enqueue(lq* pq, btn* d)
{
	struct node* newnode = (struct node*)malloc(sizeof(struct node));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		return false;
	}
	newnode->data = d;
	newnode->next = NULL;
	pq->r->next = newnode;
	pq->r = newnode;
	return true;
}
bool outqueue(lq* pq, btn** d)
{
	if (is_empty(pq))
		return false;
	*d = pq->f->next->data;
	struct node* tmp = pq->f->next;
	pq->f->next = tmp->next;
	if (pq->f->next == NULL)
		pq->r = pq->f;
	tmp->next = NULL;
	free(tmp);
	return true;
}
btn* create_tree()
{
	btn* pa, *pb, *pc, *pd, *pe;
	pa = (btn*)malloc(sizeof(btn));
	pb = (btn*)malloc(sizeof(btn));
	pc = (btn*)malloc(sizeof(btn));
	pd = (btn*)malloc(sizeof(btn));
	pe = (btn*)malloc(sizeof(btn));

	pa->plch = pb;
	pa->prch = pc;

	pb->plch = pd;
	pb->prch = pe;

	pc->plch = NULL;
	pc->prch = NULL;

	pd->plch = NULL;
	pd->prch = NULL;

	pe->plch = NULL;
	pe->prch = NULL;
	
	pa->btdata = 'a';
	pb->btdata = 'b';
	pc->btdata = 'c';
	pd->btdata = 'd';
	pe->btdata = 'e';
	return pa;
}
void level_show(btn* proot)
{
	lq* pq = queueinit();
	btn* tmp = proot;
	enqueue(pq, tmp);
	while (!is_empty(pq))
	{
		outqueue(pq, &tmp);
		if (tmp != NULL)
		{
			printf("%c ", tmp->btdata);
			if (tmp->plch != NULL)
				enqueue(pq, tmp->plch);
			if (tmp->prch != NULL)
				enqueue(pq, tmp->prch);
		}
	}
}
int main()
{
	btn* proot = create_tree();
	level_show(proot);

	return 0;
}